#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void findNext(const char* search, int* next) {
    int size, k, j;
    if(!search || (size = strlen(search)) < 1) {
        // invalid
        return;
    }

    // init
    next[0] = -1;

    k = -1, j = 0;
    while(j < size-1) {
        if(k == -1 || search[k] == search[j]) {
            k++;
            j++;
            next[j] = k;
        } else {
            k = next[k];
        }
    }
    return;
}

int kmp(const char* string, const char* search, int* next) {
    int i,j;
    i = j = 0;
    int stringLen = strlen(string);
    int searchLen = strlen(search);

    while(i<stringLen && j<searchLen) {
        if(string[i] == search[j]) {
            i++;
            j++;
        } else {
            if(j == -1) {
                i++,j++;
            } else {
                j = next[j];
            }
        }
    }

    if(j == searchLen) {
        return i-searchLen;
    }
    return -1;
}

int main() {
    const char* search = "BBA";
    int* next = (int*) malloc(strlen(search)*sizeof(int));
    memset(next, 0, strlen(search));
    findNext(search, next);
    printf("%d\n", kmp("AAAAAAbbbBBABA", search, next));
    free(next);
    return 0;
}
